{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shift 2D Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shiftGrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二维网格迁移"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m</code> 行 <code>n</code> 列的二维网格 <code>grid</code> 和一个整数 <code>k</code>。你需要将 <code>grid</code> 迁移 <code>k</code> 次。</p>\n",
    "\n",
    "<p>每次「迁移」操作将会引发下述活动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>位于 <code>grid[i][j]</code> 的元素将会移动到 <code>grid[i][j + 1]</code>。</li>\n",
    "\t<li>位于 <code>grid[i][n - 1]</code> 的元素将会移动到 <code>grid[i + 1][0]</code>。</li>\n",
    "\t<li>位于 <code>grid[m - 1][n - 1]</code> 的元素将会移动到 <code>grid[0][0]</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>k</code> 次迁移操作后最终得到的 <strong>二维网格</strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/16/e1-1.png\" style=\"height: 158px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong>grid</code> = [[1,2,3],[4,5,6],[7,8,9]], k = 1\n",
    "<strong>输出：</strong>[[9,1,2],[3,4,5],[6,7,8]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/16/e2-1.png\" style=\"height: 166px; width: 400px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong>grid</code> = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4\n",
    "<strong>输出：</strong>[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<code><strong>输入：</strong>grid</code> = [[1,2,3],[4,5,6],[7,8,9]], k = 9\n",
    "<strong>输出：</strong>[[1,2,3],[4,5,6],[7,8,9]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 <= m <= 50</code></li>\n",
    "\t<li><code>1 <= n <= 50</code></li>\n",
    "\t<li><code>-1000 <= grid[i][j] <= 1000</code></li>\n",
    "\t<li><code>0 <= k <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shift-2d-grid](https://leetcode.cn/problems/shift-2d-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shift-2d-grid](https://leetcode.cn/problems/shift-2d-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]\\n1', '[[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]]\\n4', '[[1,2,3],[4,5,6],[7,8,9]]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        # ans = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for _ in range(k):\n",
    "            pre = grid[m-1][n-1]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    grid[i][j],pre = pre,grid[i][j]\n",
    "\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                index1 = (i*n+j+k)%(m*n)\n",
    "                ans[index1//n][index1%n] = v\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        length = m*n\n",
    "        k %= length\n",
    "        \n",
    "        array = [v for row in grid for v in row]\n",
    "        array = array[length-k:] + array[:length-k]\n",
    "        for k,v in enumerate(array):\n",
    "            i = k//n\n",
    "            j = k%n\n",
    "            grid[i][j] = v\n",
    "\n",
    "        return grid\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        #copy zero\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        sx,sy=(k//m)%n,k%m\n",
    "        g =[[0]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                g[sx][sy] = grid[i][j]\n",
    "                sy+=1\n",
    "                if sy ==m:\n",
    "                    sy =0\n",
    "                    sx+=1\n",
    "                    if sx ==n:\n",
    "                        sx=0\n",
    "        return g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        tmp = []\n",
    "        cou = 0\n",
    "        for i in grid:\n",
    "            tmp.extend(i)\n",
    "        k = k%(len(tmp))\n",
    "        l = len(tmp)\n",
    "        tmp = tmp+tmp\n",
    "        #print(tmp)\n",
    "        tmp = tmp[l-k:2*l+k]\n",
    "        #print(tmp)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                grid[i][j]=tmp[cou]\n",
    "                cou+=1\n",
    "        return grid\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        reli = [[0]*w for _ in range(h)]\n",
    "        for x in range(w):\n",
    "            for y in range(h):\n",
    "                nx = (x + k) % w            \n",
    "                ny = ((x + k) // w + y) % h\n",
    "                reli[ny][nx] = grid[y][x]\n",
    "        return reli"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        p = k % (n * m)\n",
    "        ans = [[0]*n for i in range(m)]\n",
    "        if p == 0:\n",
    "            return grid\n",
    "        else:\n",
    "            for i in range(m*n):\n",
    "                if i < p:\n",
    "                    ans[i//n][i%n] = grid[(m*n - p+i)//n][(m*n - p+i)%n]\n",
    "                else:\n",
    "                    ans[i//n][i%n] = grid[(i - p)//n][(i - p)%n]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k %=m*n\n",
    "        ans =[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x,y=divmod(i*n+j+k,n)\n",
    "                ans[x%m][y]=grid[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        lst = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                lst.append(j)\n",
    "        for s in range(k):\n",
    "            temp = lst[m*n-1]\n",
    "            for i in range(m*n-1,0,-1):\n",
    "                lst[i] = lst[i-1]\n",
    "            \n",
    "            lst[0] = temp\n",
    "        count = 0\n",
    "        res = []\n",
    "        temp = []\n",
    "        for i in range(m*n):\n",
    "            if count<n:\n",
    "                temp.append(lst[i])\n",
    "                count = count+1\n",
    "            else:\n",
    "                count = 1\n",
    "                res.append(temp)\n",
    "                temp = []\n",
    "                temp.append(lst[i])\n",
    "        res.append(temp)\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        k%=m*n\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x,y=divmod(i*n+j+k,n)\n",
    "                ans[x%m][y]=grid[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            flat = sum(grid, [])\n",
    "            k %= m * n\n",
    "            flat = flat[-k:] + flat[:-k]\n",
    "            return [flat[i * n:(i + 1) * n] for i in range(m)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        k %= m * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x, y = divmod(i * n + j + k, n)\n",
    "                ans[x % m][y] = grid[i][j]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                index1 = (i*n+j+k)%(m*n)\n",
    "                ans[index1//n][index1%n] = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        k %= m*n\n",
    "        \n",
    "        x = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a, b = divmod(j+k, n)     \n",
    "                x[(i+a)%m][b] = grid[i][j]\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        res=[[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        #print(res)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                #print((i+(j+k)//len(grid[0]))%len(grid))\n",
    "                #print((j+k)%len(grid[0]))\n",
    "                res[(i+(j+k)//len(grid[0]))%len(grid)][(j+k)%len(grid[0])]=grid[i][j]\n",
    "        #print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        k %= m * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x, y = divmod(i * n + j + k, n)\n",
    "                ans[x % m][y] = grid[i][j]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nums = [grid[i][j] for i in range(m) for j in range(n)]\n",
    "        k %= m * n\n",
    "        nums = nums[-k:] + nums[:-k]\n",
    "        return [[nums[i * n + j] for j in range(n)]for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        new_grid = deepcopy(grid)\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ni = (i + (j + k) // n) % m\n",
    "                nj = (j + k) % n\n",
    "                new_grid[ni][nj] = grid[i][j]\n",
    "        return new_grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row = len(grid)\n",
    "        queue = len(grid[0])\n",
    "        ans = [[0] * queue for i in range(row)]\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(queue):\n",
    "                div,mod = divmod((i*queue+j+k)%(row*queue),queue)\n",
    "                ans[div][mod] = grid[i][j]\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        k %= m * n\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x, y = divmod(i * n + j + k, n)\n",
    "                ans[x % m][y] = grid[i][j]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                index = (i * n + j + k)%(m * n)\n",
    "                ans[index // n][index % n] = grid[i][j]\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        a=len(grid)\n",
    "        b=len(grid[0])\n",
    "        if(k==0):\n",
    "            return grid\n",
    "        for l in range(k):\n",
    "            gg=copy.deepcopy(grid)\n",
    "            for i in range(a):\n",
    "                if(i==a-1):\n",
    "                    gg[0][0]=grid[a-1][b-1]\n",
    "                else:\n",
    "                    gg[i+1][0]=grid[i][b-1]\n",
    "                for j in range(b-1):\n",
    "                    gg[i][j+1]=grid[i][j]\n",
    "            grid=copy.deepcopy(gg)\n",
    "        return gg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        # 展开成一维数组\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        elementsNums = m * n\n",
    "\n",
    "        k %= elementsNums\n",
    "\n",
    "        array1 = []\n",
    "        for row in grid:\n",
    "            array1 += row\n",
    "        \n",
    "        temp = array1[elementsNums - k:] + array1[:elementsNums - k]\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            res.append(temp[i*n:(i+1)*n])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        new_grid = deepcopy(grid)\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nj = j + k\n",
    "                ni = i\n",
    "                ni += nj // n\n",
    "                nj = nj % n\n",
    "                ni = ni % m\n",
    "                new_grid[ni][nj] = grid[i][j]\n",
    "        return new_grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = [[0]* n for _ in range(m)]\n",
    "        for i , row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                index1 = (i*n+j+k)%(m*n)\n",
    "                ans[index1//n][index1%n] = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        k %= m*n\n",
    "        \n",
    "        x = [[0 for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a, b = divmod(j+k, n)     \n",
    "                x[(i+a)%m][b] = grid[i][j]\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        grid = sum(grid, [])\r\n",
    "        k %= m * n\r\n",
    "        grid = grid[-k:] + grid[:-k]\r\n",
    "        return [grid[i * n : (i + 1) * n] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        while k > 0:\n",
    "            for i in range(len(grid)):\n",
    "                n = grid[i].pop(-1)\n",
    "                grid[i].insert(0, n)\n",
    "            n = grid[-1][0]\n",
    "            for i in range(1, len(grid)):\n",
    "                grid[-i][0] = grid[-i - 1][0]\n",
    "            grid[0][0] = n\n",
    "            k -= 1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index = (i * n + j + k) % (m * n)\n",
    "                f[index // n][index % n] = v\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        element_num = len(grid) * len(grid[0])\n",
    "        k %= element_num\n",
    "        now_lst = []\n",
    "        for line in grid:\n",
    "            now_lst.extend(line)\n",
    "        now_lst = now_lst[-k:] + now_lst[: -k]\n",
    "        result = []\n",
    "        for i in range(len(grid)):\n",
    "            result.append(now_lst[i * len(grid[0]): (i + 1) * len(grid[0])])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [element for hang in grid for element in hang]\n",
    "\n",
    "        for _ in range(k):\n",
    "            ans.insert(0, ans.pop())\n",
    "\n",
    "        return [ans[i * n: i * n + n] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        k %= m * n\n",
    "        return [[grid[(i*n+j-k)//n][(i*n+j-k)%n] for j in range(n)] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m * n):\n",
    "            r,c = i // n, i % n\n",
    "            new_r,new_c = (k % (m * n)) // n, k % n\n",
    "            res[new_r][new_c] = grid[r][c]\n",
    "            k += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        lst = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                lst.append(j)\n",
    "        for s in range(k):\n",
    "            temp = lst[m*n-1]\n",
    "            for i in range(m*n-1,0,-1):\n",
    "                lst[i] = lst[i-1]\n",
    "            \n",
    "            lst[0] = temp\n",
    "        count = 0\n",
    "        res = []\n",
    "        temp = []\n",
    "        for i in range(m*n):\n",
    "            if count<n:\n",
    "                temp.append(lst[i])\n",
    "                count = count+1\n",
    "            else:\n",
    "                count = 1\n",
    "                res.append(temp)\n",
    "                temp = []\n",
    "                temp.append(lst[i])\n",
    "        res.append(temp)\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def transfer(grid):\n",
    "            for i in range(len(grid)):\n",
    "                line = grid[i]\n",
    "                temp = line[-1]\n",
    "                for j in range(len(line)-1,-1,-1):\n",
    "                    line[j] = line[j-1]\n",
    "                line[0] = temp\n",
    "            temp = grid[-1][0]\n",
    "            for i in range(len(grid)-1,-1,-1):\n",
    "                grid[i][0] = grid[i-1][0]\n",
    "            grid[0][0] = temp\n",
    "            return grid\n",
    "        for i in range(k):\n",
    "            grid = transfer(grid)\n",
    "        return grid\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for _ in range(k):\n",
    "            tmp = grid[m-1][n-1]\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n-1, -1, -1):\n",
    "                    if j == 0:\n",
    "                        if i == 0:\n",
    "                            grid[0][0] = tmp\n",
    "                        else:\n",
    "                            grid[i][j] = grid[i-1][-1]\n",
    "                    else:\n",
    "                        grid[i][j] = grid[i][j-1]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=[[0] * n for _ in range(m)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,v in enumerate(row):\n",
    "                index1=(i*n+j+k)%(m*n)\n",
    "                ans[index1//n][index1%n]=v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        r=0\n",
    "        k=k%(m*n)\n",
    "        #if k==0:\n",
    "            #return grid\n",
    "        \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                l=(i*n+j+k)%(m*n)\n",
    "               # print(i,j,l)\n",
    "                x=l//n\n",
    "                y=l%n\n",
    "                ans[x][y]=grid[i][j]\n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        k = k %(rownum*colnum)\n",
    "        numlist = []\n",
    "        reslist = []\n",
    "        resgrid = []\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                numlist.append(grid[i][j])\n",
    "        listlen = len(numlist)\n",
    "        for idx in range(listlen-k, listlen):\n",
    "            reslist.append(numlist[idx])\n",
    "        for idx in range(listlen-k):\n",
    "            reslist.append(numlist[idx])\n",
    "        for idx, item in enumerate(reslist):\n",
    "            if idx % colnum == 0:\n",
    "                resgrid.append([])\n",
    "            resgrid[idx//colnum].append(item)\n",
    "        return resgrid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def shiftGrid1(grid):\n",
    "            m = len(grid)\n",
    "            n = len(grid[0])\n",
    "            tmp = [[0]*n for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i == 0 and j == 0:\n",
    "                        tmp[i][j] = grid[m-1][n-1]\n",
    "                    elif j == 0:\n",
    "                        tmp[i][j] = grid[i-1][n-1]\n",
    "                    else:\n",
    "                        tmp[i][j] = grid[i][j-1]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    grid[i][j] = tmp[i][j]\n",
    "            return\n",
    "        time = k\n",
    "        while time:\n",
    "            shiftGrid1(grid)\n",
    "            time -= 1\n",
    "        return grid\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def shiftGrid1(grid):\n",
    "            m = len(grid)\n",
    "            n = len(grid[0])\n",
    "            tmp = deepcopy(grid)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i == 0 and j == 0:\n",
    "                        tmp[i][j] = grid[m-1][n-1]\n",
    "                    elif j == 0:\n",
    "                        tmp[i][j] = grid[i-1][n-1]\n",
    "                    else:\n",
    "                        tmp[i][j] = grid[i][j-1]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    grid[i][j] = tmp[i][j]\n",
    "            return\n",
    "        time = k\n",
    "        while time:\n",
    "            shiftGrid1(grid)\n",
    "            time -= 1\n",
    "        return grid\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        new_grid = deepcopy(grid)\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nj = j + k\n",
    "                ni = i\n",
    "                if nj >= n:\n",
    "                    ni += nj // n\n",
    "                    nj = nj % n\n",
    "                if ni >= m:\n",
    "                    ni = ni % m\n",
    "                new_grid[ni][nj] = grid[i][j]\n",
    "        return new_grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0:\n",
    "                    cur = (i * n + j + k) % (m * n)\n",
    "                    temp = grid[i][j]\n",
    "                    while visited[cur // n][cur % n] == 0:\n",
    "                        grid[cur // n][cur % n], temp = temp, grid[cur // n][cur % n]\n",
    "                        visited[cur // n][cur % n] = 1\n",
    "                        cur = (cur + k) % (m * n)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         ans = [[0] * n for _ in range(m)]\n",
    "#         for row in range(m):\n",
    "#             for col in range(n):\n",
    "#                 ans[row][col] = grid[row][col]\n",
    "#         for row in range(m):\n",
    "#             for col in range(n):\n",
    "#                 if col + 1 < n:\n",
    "#                     grid[row][col + 1] = ans[row][col]\n",
    "#                 if row + 1 < m:    \n",
    "#                     grid[row + 1][0] = ans[row][n - 1]\n",
    "#             grid[0][0] = ans[m - 1][n - 1]\n",
    "#             for row in range(m):\n",
    "#                 for col in range(n):\n",
    "#                     ans[row][col] = grid[row][col]\n",
    "#         return grid\n",
    "# class Solution:\n",
    "#     def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "#         m, n = len(grid), len(grid[0])\n",
    "#         ans = [[0] * n for _ in range(m)]\n",
    "#         for i, row in enumerate(grid):\n",
    "#             for j, v in enumerate(row):\n",
    "#                 index1 = (i * n + j + k) % (m * n)\n",
    "#                 ans[index1 // n][index1 % n] = v\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        alist = list()\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        for i in range(row):\n",
    "            alist += grid[i]\n",
    "        k = k % len(alist)\n",
    "        l = alist[-k:]\n",
    "        r = alist[0:-k]\n",
    "        ref = l+r\n",
    "        res = list()\n",
    "        for i in range(0,len(ref),col):\n",
    "            sub = ref[i:i+col]\n",
    "            res.append(sub)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        rows,cols = len(grid),len(grid[0])\n",
    "        res = [[0 for _ in range(cols)] for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                new_i = (i  + (j + k) // cols) % rows\n",
    "                new_j = (j + k) % cols\n",
    "                res[new_i][new_j] = grid[i][j]\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        lst = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                lst.append(grid[i][j])\n",
    "        \n",
    "        for i in range(k):\n",
    "            ele = lst.pop()\n",
    "            lst.insert(0, ele)\n",
    "        \n",
    "        res = [[0] * m for _ in range(n)]\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res[i][j] = lst[idx]\n",
    "                idx += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\r\n",
    "        self.r = len(grid)\r\n",
    "        self.c = len(grid[0])\r\n",
    "        # self.res = [[0 for _ in range(self.c)] for _ in range(self.r)]\r\n",
    "\r\n",
    "        for i in range(k):\r\n",
    "            grid = self.shift(grid)\r\n",
    "\r\n",
    "        return grid\r\n",
    "    \r\n",
    "    def shift(self, grid: List[List[int]]) -> List[List[int]]:\r\n",
    "\r\n",
    "        lastc = [row[-1] for row in grid]\r\n",
    "        rightbottom = grid[self.r-1][self.c-1]\r\n",
    "\r\n",
    "        lastc[1:self.r] = lastc[0:self.r-1]\r\n",
    "        lastc[0] = rightbottom\r\n",
    "\r\n",
    "        for row in range(self.r):\r\n",
    "            for col in range(self.c - 2 , -1, -1):\r\n",
    "                grid[row][col+1] = grid[row][col]\r\n",
    "        for row in range(self.r):\r\n",
    "            grid[row][0] = lastc[row]\r\n",
    "\r\n",
    "        return grid\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0:\n",
    "                    cur = (i * n + j + k) % (m * n)\n",
    "                    temp = grid[i][j]\n",
    "                    while visited[cur // n][cur % n] == 0:\n",
    "                        grid[cur // n][cur % n], temp = temp, grid[cur // n][cur % n]\n",
    "                        visited[cur // n][cur % n] = 1\n",
    "                        cur = (cur + k) % (m * n)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return [[grid[(i*n+j-k%(m*n))//n][(i*n+j-k%(m*n))%n] for j in range(n)] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[[1,2,3],[4,5,6],[7,8,9]]\n",
    "1\n",
    "[[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]]\n",
    "4\n",
    "[[1,2,3],[4,5,6],[7,8,9]]\n",
    "9\n",
    "\n",
    "m == grid.length\n",
    "n == grid[i].length\n",
    "1 <= m <= 50\n",
    "1 <= n <= 50\n",
    "-1000 <= grid[i][j] <= 1000\n",
    "0 <= k <= 100\n",
    "\n",
    "Array, Matrix, Simulation\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        for _ in range(k):\n",
    "            prv = grid[-1][-1]\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    tmp = grid[i][j]\n",
    "                    grid[i][j] = prv\n",
    "                    prv = tmp\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        for i in range(k):\n",
    "            for j in range(len(grid)):\n",
    "                grid[j].insert(0,grid[j-1][-1])\n",
    "            for k in range(len(grid)):\n",
    "                del grid[k][-1]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        g=[j for i in grid for j in i]\n",
    "        k = k % (m * n)\n",
    "        g=g[-k:]+g[:-k]\n",
    "        x=[]\n",
    "        a=0\n",
    "        for j in range(m):\n",
    "            x+=[g[a:n]]\n",
    "            a+=len(grid[0])\n",
    "            n+=len(grid[0])\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        for i in range(k):\n",
    "            # print(grid)\n",
    "            grid = list(zip(*grid))\n",
    "            # print(grid)\n",
    "            tmp = grid[-1]\n",
    "            grid[1:] = grid[:-1]\n",
    "            grid[0] = tmp[-1:] + tmp[:-1]\n",
    "            grid = list(zip(*grid))\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = m*n\n",
    "        ret = [[0]*n for _ in range(m)]\n",
    "        \n",
    "        v = (tot - k) % tot\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ret[i][j] = grid[v//n][v%n]\n",
    "                v += 1\n",
    "                v %= tot\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        arr = []\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                arr.append(grid[i][j])\n",
    "        tmp = []\n",
    "        k %= len(arr) \n",
    "        for i in range(len(arr) - k, len(arr)):\n",
    "            tmp.append(arr[i])\n",
    "        for i in range(len(arr)-k-1,-1,-1):\n",
    "            arr[i+k] = arr[i] \n",
    "        for i in range(k):\n",
    "            arr[i] = tmp[i] \n",
    "        c = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = arr[c]\n",
    "                c+=1 \n",
    "        return grid \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if k%(m*n) == 0:\n",
    "            return grid\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, v in enumerate(row):\n",
    "                index1 = (i * n + j + k) % (m * n)\n",
    "                ans[index1 // n][index1 % n] = v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        grid2=[[0]*len(grid[0]) for i in range(len(grid))]\n",
    "        n=len(grid[0])\n",
    "        m=len(grid)\n",
    "        for s in range(k):\n",
    "            if s%2==0:\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        if j==n-1 and i==m-1:\n",
    "                            grid2[0][0]=grid[i][j]\n",
    "                        elif j==n-1:\n",
    "                            grid2[i+1][0]=grid[i][j]\n",
    "                        else:\n",
    "                            grid2[i][j+1]=grid[i][j]\n",
    "            else:\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        if j==n-1 and i==m-1:\n",
    "                            grid[0][0]=grid2[i][j]\n",
    "                        elif j==n-1:\n",
    "                            grid[i+1][0]=grid2[i][j]\n",
    "                        else:\n",
    "                            grid[i][j+1]=grid2[i][j]\n",
    "        if k%2==1:\n",
    "            return grid2\n",
    "        else:\n",
    "            return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        grid = [j for i in grid for j in i]\n",
    "        for _ in range(k):\n",
    "            i = grid.pop()\n",
    "            grid.insert(0, i)\n",
    "        return [[grid.pop(0) for _ in range(col)] for _ in range(row)]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        arr = []\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                arr.append(grid[i][j])\n",
    "        tmp = []\n",
    "        k %= len(arr) \n",
    "        for i in range(len(arr) - k, len(arr)):\n",
    "            tmp.append(arr[i])\n",
    "        for i in range(len(arr)-k-1,-1,-1):\n",
    "            arr[i+k] = arr[i] \n",
    "        for i in range(k):\n",
    "            arr[i] = tmp[i] \n",
    "        c = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = arr[c]\n",
    "                c+=1 \n",
    "        return grid \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        nums = []\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        for i in range(rows):\n",
    "            nums.extend(grid[i])\n",
    "\n",
    "        cnt = 0\n",
    "        while cnt < k:\n",
    "            cnt += 1\n",
    "            num = nums.pop()\n",
    "            nums.insert(0, num)\n",
    "        res = []\n",
    "        for i in range(rows):\n",
    "            tmp = []\n",
    "            for i in range(cols):\n",
    "                tmp.append(nums.pop(0))\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        r=0\n",
    "        k=k%(m*n)\n",
    "        #if k==0:\n",
    "            #return grid\n",
    "        \n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                l=(i*n+j+k)%(m*n)\n",
    "                print(i,j,l)\n",
    "                x=l//n\n",
    "                y=l%n\n",
    "                ans[x][y]=grid[i][j]\n",
    "\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        el = [row[j] for row in grid for j in range(n)]\n",
    "        \n",
    "        k = k % len(el)\n",
    "        el = el[-k:] + el[:-k]\n",
    "        print(el)\n",
    "\n",
    "        i = j = 0\n",
    "        for num in el:\n",
    "            if 0<= j < n:\n",
    "                grid[i][j] = num\n",
    "            else:\n",
    "                i += 1\n",
    "                j = 0\n",
    "                grid[i][j] = num\n",
    "            j += 1\n",
    "        \n",
    "        return grid\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mn = m*n\n",
    "        k = k % mn\n",
    "\n",
    "        self.reverse(grid, 0, mn-1)\n",
    "        self.reverse(grid, 0, k-1)\n",
    "        self.reverse(grid, k, mn-1)\n",
    "\n",
    "        return grid\n",
    "\n",
    "    def reverse(self, grid, left, right):\n",
    "        while left < right:\n",
    "            tmp = self.get(grid, left)\n",
    "            self.set(grid, left, self.get(grid, right))\n",
    "            self.set(grid, right, tmp)\n",
    "\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "    def get(self, grid, index):\n",
    "        n = len(grid[0])\n",
    "        row = index // n\n",
    "        col = index % n\n",
    "        print(index, n)\n",
    "        return grid[row][col]\n",
    "    \n",
    "    def set(self, grid, index, val):\n",
    "        n = len(grid[0])\n",
    "        row = index // n\n",
    "        col = index % n\n",
    "        grid[row][col] = val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        g_lst = []\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            g_lst += grid[i]\n",
    "\n",
    "        for i in range(k):\n",
    "            g_lst = [g_lst[-1]] + g_lst[:-1]\n",
    "        print(g_lst)\n",
    "        res = []\n",
    "        for j in range(0, len(g_lst), len(grid[0])):\n",
    "            res.append(g_lst[j : j + len(grid[0])])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if k%(m*n) == 0:\n",
    "            return grid\n",
    "        nums = []\n",
    "        # nums = [ num for num in row for row in range(grid)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nums.append(grid[i][j])\n",
    "        k = k%(m*n )\n",
    "        \n",
    "        nums = nums[n*m-k:]+nums[:n*m-k]\n",
    "        idx = 0\n",
    "        print(nums)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = nums[idx]\n",
    "                idx += 1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "      for i in range(k):\n",
    "        \n",
    "        grid = list(zip(*grid))\n",
    "        tmp = list(grid[-1])\n",
    "        grid[1:] = grid[:-1]\n",
    "        grid[0] = tmp[-1:]+tmp[:-1]\n",
    "        grid = list(zip(*grid))\n",
    "      return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        lst = []\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                lst.append(grid[i][j])\n",
    "        lst1 = [0] * len(lst)\n",
    "        for i, num in enumerate(lst):\n",
    "            t = (i + k) % len(lst)\n",
    "            lst1[t] = num \n",
    "        print(lst1)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                grid[i][j] = lst1[i * len(grid[0]) + j]\n",
    "        return grid"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
